package 力扣._2070_每一个查询的最大美丽值;

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        Arrays.sort(items, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]!=o2[0])
                    return o1[0]-o2[0];
                else
                    return o2[1]-o1[1]; // 按最大美丽数降序
            }
        });

        // 当前价格最大美丽数, 将同一价格的最大美丽数设置为改价格所有的，便于查询
        for (int i = 1; i < items.length; i++) {
            if(items[i][1] < items[i-1][1]){
                items[i][1]=items[i-1][1];
            }
        }

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int k = queries[i];
            // 二分
            int mid,l=0,r=items.length-1;
            while (l<=r){
                mid = (l+r)/2;
                if(items[mid][0]<k) {
                    l = mid+1;
                } else if (items[mid][0]>k) {
                    r = mid-1;
                }else {
                    result[i]=items[mid][1];
                    break;
                }
            }
            if(l>r){// 如果没找到价格，-》找更小的价格
                if(r>=0)
                    result[i]=items[r][1];
                else
                    result[i]=0;
            }
        }
        return result;

    }

    public static void main(String[] args) {
        // item = [[1,2],[3,2],[2,4],[5,6],[3,5]]
        // queries// [1,2,3,4,5,6]
        //int[][] items = {{1,2},{3,2},{2,4},{5,6},{3,5}};
        //int[] queries = {1,2,3,4,5,6};

        // items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
//        int[][] items = {{1,2},{1,2},{1,3},{1,4}};
//        int[] queries = {1};

        // items = [[10,1000]], queries = [5]
        int[][] items = {{10,1000}};
        int[] queries = {5};

        int[] result = new Solution().maximumBeauty(items, queries);
        for (int i : result) {
            System.out.println(i);
        }
    }
}